package leetcode_21_40;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class nextPermutation_31 {
    /**
     * 思路是从最后一位开始比较，逐级向左进行判断
     * 1ms
     * 击败34%
     * @param nums
     */
    public static void nextPermutation(int[] nums) {
        int index=nums.length-1;
        List<Integer>nums1=new ArrayList<>();
        //向前一位比较
        // 124321   -》 131224
        while (index>0){
            nums1.add(nums[index]);                     //集合中是升序排列的需要操作的数字   1 2 3 4
            if(nums[index]>nums[index-1]){          //直到index处数字大于前一位，退出循环
                if(index==nums.length-1){               //如果是最后一位直接大于前一位，交换返回
                    int t=nums[index];  //142321
                    nums[index]=nums[index-1] ;
                    nums[index-1]=t;
                    return;
                }
                break;
            }
            index--;  //需要继续判断前一位
        }
        if(index==0){            //说明是一个最大的排列，此时返回最小的排列    即3 2 1 返回 1 2 3
            for(int i=0, j=nums.length-1;i<nums.length/2;i++,j--){
                int temp=nums[i];
                nums[i]=nums[j] ;
                nums[j]=temp;
            }
            return;
        }
        //找到升序集合nums1中比前一位更大的最小数字   ，交换数字        nums: 134321  nums1: 1 2 2 4
        for(int i=0;i<nums1.size();i++){
            if(nums1.get(i)> nums[index-1]){
                int t=nums[index-1];  //142321
                nums[index-1]=nums1.get(i) ;
                nums1.set(i,t);
                break;
            }
        }
        //因为交换后集合仍然是升序，直接赋值即可         1 3 + 1 2 2 4
        for (int i:nums1) {
            nums[index++]=i;
        }
    }

    /**
     * 官方0ms题解
     * 思路和我的一模一样，但是代码实现有所不同
     * @param nums
     */
    public void nextPermutation2(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {   //直到i 处数字小于后一位
            i--;
        }
        if (i >= 0) {                                  //这里很巧妙，将降序部分倒序
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {        //找到后边部分，升序数组中比前一位更大的最小数字，交换数字
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
